package com.lhcai.lc.other;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lhcstart
 * @create 2023-02-27 10:26
 */

/**
 * 二分法解决问题
 */
public class lc373_1 {
    int[] n1, n2;
    int len1, len2;

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

        n1 = nums1;
        n2 = nums2;
        len1 = nums1.length;
        len2 = nums2.length;
        List<List<Integer>> ans = new ArrayList<>();
        int l = nums1[0] + nums2[0], r = nums1[len1 - 1] + nums2[len2 - 1];
        //循环判断直到l>=r
        while (l < r) {
            int mid = (int) (0L + l + r >> 1);
            if (check(mid, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        //将r的值赋给x,则小于x的都是符合条件的
        int x = r;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (n1[i] + n2[j] < x) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(n1[i]);
                    temp.add(n2[j]);
                    ans.add(temp);
                } else {
                    break;
                }
            }
        }

        for (int i = 0; i < len1 && ans.size() < k; i++) {
            int a = n1[i], b = x - a;
            int c = -1, d = -1;
            l = 0;
            r = len2 - 1;
            while (l < r) {
                int mid = (int) (0L + l + r >> 1);
                if (n2[mid] >= b) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }

            if (n2[r] != b) {
                continue;
            }
            c = r;
            l = 0;
            r = len2 - 1;
            while (l < r) {
                int mid = (int) (0L + l + r + 1) >> 1;
                if (nums2[mid] <= b) l = mid;
                else r = mid - 1;
            }
            d = r;
            for (int p = c; p <= d && ans.size() < k; p++) {
                List<Integer> temp = new ArrayList<>();
                temp.add(a);
                temp.add(b);
                ans.add(temp);
            }
        }
        return ans;
    }

    //判断小于二分值的个数（左侧），大于等于K返回true,小于K返回false
    boolean check(int x, int k) {
        int ans = 0;
        for (int i = 0; i < len1 && ans < k; i++) {
            for (int j = 0; j < len2 && ans < k; j++) {
                if (n1[i] + n2[j] <= x) {
                    ans++;
                } else {
                    break;
                }
            }
        }
        return ans >= k;
    }


}
